package algorithm.dynamic_planning.leetcode;

import java.util.Arrays;

/**
 * @author yuisama
 * @date 2022/12/09 12:13
 * dp 解决最小下降路径和问题
 **/
public class Num931_MinFallingPathSum {
    // 取最小值选整型最大值
    int res = Integer.MAX_VALUE;
    // 备忘录
    int[][] memo;
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        memo = new int[n][n];
        // 初始化备忘录
        for (int i = 0; i < n; i++) {
            Arrays.fill(memo[i],66666);
        }
        // 终点可能在最后一行的任意一列
        for (int j = 0; j < n; j++) {
            res = Math.min(res,dp(matrix,n - 1,j));
        }
        return res;
    }
    // 从matrix[0][0] 下降到matrix[i][j]位置的最短路径和
    private int dp(int[][] matrix, int i, int j) {
        // 1.处理非法索引
        if (i < 0 || j < 0 || i >= matrix.length || j >= matrix.length) {
            return 99999;
        }
        // 2.base case
        if (i == 0) {
            // 下降到第一行第j列的最短路径，就是其本身
            return matrix[i][j];
        }
        // 查备忘录
        if (memo[i][j] != 66666) {
            return memo[i][j];
        }
        // matrix[i][j]只能从matrix[i - 1][j - 1] matrix[i - 1][j]
        // matrix[i - 1][j + 1] 这三个位置转移来
        memo[i][j] = matrix[i][j] + min(dp(matrix,i - 1,j),dp(matrix,i - 1,j - 1)
                ,dp(matrix,i - 1,j + 1));
        return memo[i][j];
    }

    private int min(int x, int y, int z) {
        int tempMin = Math.min(x,y);
        return Math.min(tempMin,z);
    }
}